1. Field of the Invention
The present invention is related to elimination of unnecessary data retransmissions. More particularly, the present invention is related to preventing unnecessary retransmissions from being sent from a terminal, such as an internet host computer, on a slow link.
2. Related Art
Data communications systems typically employ a send and acknowledge scheme, whereby a first terminal sends data packets to a second terminal and the second terminal responds with acknowledge signals. Generally, if the first terminal does not receive an acknowledge signal within a prescribed period of time, the first terminal retransmits the data packet under the assumption that the initial transmission was not received by the second terminal.
The prescribed period of time is often based on an expected round trip time it takes for the data packet to travel to the second terminal and for the corresponding acknowledge signal to return to the first terminal. Round trip times are typically estimated by sending a sample data packet and measuring the time it takes to receive an acknowledge.
Some communication links include what are referred to herein as "slow links." Slow links are communication links that add some amount of latency to the round trip time, wherein the latency depends upon the amount of data being sent. Small sample data packets are often unaffected by latency of slow links. Estimates of round trip times that rely only on small data packet round trip times thus underestimate actual round trip times. As a result, round trip times expire prematurely, causing unnecessary retransmissions of data. Unnecessary retransmissions clog communication links and cause other problems as well. In many situations, the user of the second terminal has no control over the first terminal and thus has no ability to require or ensure that the first terminal correctly estimates round trip time.
Unnecessary data retransmissions are a problem for many types of data communications. In order to more fully understand the cause, effects and solution to unnecessary data retransmissions, data retransmissions are described below within the context of an internet communication system. The examples below are provided to illustrate the problem and solution of unnecessary data retransmissions. They are not intended to limit the scope of the present invention.
An internet communication system includes interconnected networks that support communication among host computers using internet protocols. A host computer typically executes application programs on behalf of users, employing network and/or internet communication services in support of this function. Internet host computers can span a wide range of sizes, speed and functions and can range in size from small microprocessors through workstations to mainframes and super computers. In function, they range from single-purpose hosts (such as terminal servers) to full-service hosts that support a variety of online network services, typically including remote login, file transfer and electronic mail.
The internet is thus a network of networks where each host is directly connected to some particular network or networks. A connection between a host and the internet is only conceptual. Two hosts on the same network communicate with each other using the same setup protocols that they would use to communicate with hosts on distant networks.
Individual or remote users can access the internet from remote terminals (e.g., personal computers, laptop computers, etc.) via internet service providers (ISP). An ISP can also serve as an internet host computer. Remote users are typically connected to ISPs through a public service telecommunications network (PSTN). A coupling between a remote user and a PSTN is typically a slow link such as a PSTN cellular link or a code division multiple access (CDMA) cellular link, which can limit transmission to nominal rates such as, for example, 1200 bits per second (bps), 2400 bps, 4800 bps, 9600 bps, 14,400 bps, etc. These systems are referred to as slow links because communications through these slow links tend to be slower than communications between hosts and between hosts and ISPs on the internet.
When a host computer sends a stream of data packets through an ISP to a remote terminal, the slow link between the ISP and the remote terminal creates a bottleneck where data packets from the host congregate while waiting to be sent to the remote terminal over the slow link. As a result, slow links limit data throughput.
A basic objective of internet design is to tolerate a wide range of network characteristics such as, for example, bandwidth, delay, packet loss, packet reordering and maximum packet size. Accordingly, an internet engineering task force has generated communication specifications for internet host computers. Some of these specifications are available as Request For Comments (RFCs), that are available on the internet at, for example, http://www.nexor.com/ public/rfc/rfcs/rfc. Of particular interest here is an RFC 1122, available on the internet at http://www.nexor.com/public/rfc/rfcs/rfc1122.txt, incorporated herein in its entirety by reference.
These RFCs provide specifications for, among other things, a transmission control protocol (TCP) used by internet host computers. TCP is the primary protocol for the internet. TCP provides reliable, in-sequence delivery of a full-duplex stream of octets (8-bit bytes). TCP is used by applications that require reliable, connection-oriented transport service, e.g., mail (SMTP), file transfer (FTP), and virtual terminal service (Telnet).
Host computers typically maintain a sliding window within which they transmit data packets. Under RFC 1122, in order to prevent bottlenecks, host computers wait for an acknowledgment from a remote terminal when a data packet is sent. Host computers use the acknowledge signals to slide the window and transmit more data.
Host computers typically set a round trip timer based on an estimated round trip time that it takes for a data packet to travel to a remote user and for an acknowledgment from the remote user to travel back to the host computer. When a host computer sends a data packet, the round trip timer is set. If an acknowledgment is not received by the expiration of the round trip timer, the data packet is resent on the assumption that the data packet was not received by the remote terminal. According to RFC 1122, section 4.2.2.15, titled "Retransmission Timeout: RFC-793 section 3.7",
Recent Work by Jacobson [TCP:7] on Internet Congestion and TCP Retransmission Stability has produced a transmission algorithm combining "slow start" with "congestion avoidance". A TCP MUST implement this algorithm.
For purposes of the present invention, it is assumed that, when a host computer implements a retransmission timeout algorithm as required by RFC 1122, transmissions from internet host computers to remote users are optimized. In other words, it is assumed that where a host computer follows the requirements of RFC 1122, round trip times are properly estimated.
However, it has been determined that at least some internet host computers (hereinafter "non-compliant host computers" or "non-compliant hosts") do not employ, or do not properly employ, algorithms for optimizing data retransmissions. More specifically, it is believed that non-compliant host computers do not take slow links into account when setting round trip timers.
A host computer should calculate round trip time based on the sum of the actual round trip time of a small (e.g., 1 byte) data packet and based on any slow link latency in the system. Small data packets are typically not affected by slow links because their small size permits them to be sent over the slow link in a single send operation and because they are typically the first data sent to a slow link. Being the first data sent to a slow link means there is no existing bottle neck at the slow link which might otherwise slow transmission of the test data.
Based on examination of actual transmitted data packets, it appears that non-compliant host computers set their round trip timers based only on the round trip time of a small (e.g., 1 byte) test packet. When a non-compliant host computer thereafter sends non-test data packets, which are typically much larger than 1 byte, the data packets get delayed at the slow link. Since the non-compliant host failed to take the slow link into account, the round trip timer expires before receipt of an acknowledgment signal from the remote terminal. The non-compliant host then retransmits the data packet under the assumption that the first data packet was not received by the remote terminal. Unnecessary retransmitted data packets lead to additional latency at the slow link.
In addition to increasing the delay at slow links, non-compliant hosts also mistakenly re-estimate round trip times based on acknowledgment data. When a non-compliant host sends a data packet, it also incorrectly sets its round trip timer. As a result of incorrectly setting its round trip timer, the round trip timer expires before receipt of an acknowledge from the remote terminal. When the round trip timer expires, the non-compliant host retransmits the data packet and resets the round trip timer.
When the first data packet is eventually received by the remote terminal, the remote terminal sends an acknowledge signal. Since the non-compliant host computer receives the acknowledge after retransmitting the data packet and after resetting the round trip timer, the non-compliant host mistakenly interprets the acknowledge as an acknowledgment of receipt of the retransmitted data packet rather than the initial data packet. The non-compliant host then re-estimates the round trip time as the time when it retransmitted the data packet to the time it received the acknowledge to the initial data packet. As a result, the non-compliant host expects to receive acknowledgment of subsequently transmitted data packets faster than before and, thus, retransmits subsequent data packets at a higher rate than before, further adding to the bottleneck at the slow link. It has been observed that unnecessary retransmissions from a non-compliant host computer can reduce the effective rate of data transmission from a nominal rate of 14.4 kbps to an actual data rate of 4-5 kbps or less.
One solution is to ensure that all internet host computers implement a compliant round trip timer scheme such as, for example, that specified in RFC 1122. However, no such mechanism or procedure currently exists.
What is needed is a system, method and computer program product for optimizing data transfers from host computers over slow links.